In the case of digital data transmissions, cyclic redundancy checks are frequently carried out in order to detect errors, which can occur during the data transmission process. In this case, data signals are transmitted in blocks, and a redundant code is produced from the data in each block and is added to the block for error detection or correction. In most cases, a so-called CRC code (cyclic redundancy check) is derived from the payload data in a block as a cyclic redundant code, using a predetermined algorithm. The CRC codes are produced by multiplication of a payload data signal sequence by a so-called generator polynomial. After reception of the code word, it is divided by the generator polynomial. If the received code word has been transmitted correctly, then the division process does not produce any remainder. Conversely, if the division process results in a remainder, then this confirms that the transmission was not correct.
Cyclic codes such as CRC codes are primarily of major interest for this application because the multiplication and division of polynomials can be carried out relatively easily by means of so-called linear feedback shift registers (LFSR). Multiplication by the generator polynomial thus makes it possible to generate code words, with the original information word being reproduced by the division of these code words, and the result being checked for errors at the same time. U.S. Pat. No. 5,748,652 describes, for example, a circuit for cyclic redundancy checking for detection and correction of errors in a data stream. In this case, in the receiver, the data stream is entered in a linear feedback shift register in which a division process is carried out by means of the generator polynomial. If a faulty code word is divided in this circuit, then the remainder produced after division by the generator polynomial remain in the memory cells in the shift register once the code word has been processed. Only if a correct code word has been entered is the value in all of the memory cells zero after the division process. This division remainder, which is also called the syndrome (polynomial), is then passed to an OR gate, whose output signal is passed to a decoder as an activation signal. The syndrome is passed to the decoder and, if the decoder is activated, is linked with the input data word in an EXCLUSIVE-OR circuit, thus producing a corrected data stream.
In order to improve the transmission reliability and eavesdropping protection, the data to be transmitted is subjected at the transmitter end to a channel coding method, in which the data to be transmitted has redundancy deliberately added to it. If so-called convolutional coding is used as the coding method, in which the redundancy is formed continuously by linking (convolution) of the information, then the efficient Viterbi algorithm is generally used in the decoder at the receiver end. It has been found that a low error rate can be achieved by first of all carrying out a CRC block coding process, after which a convolutional coding process is carried out on the block-coded data. In the case of a linked channel coding method such as this, a number of CRC bits are generally first of all added to the information to be transmitted, by means of a block code. The information that has been coded in this way is then coded by means of a convolutional coder. At the receiver end, the data sequence supplied to the convolutional coder at the transmitter end is then deduced recursively in a decoder by means of the Viterbi traceback algorithm.
The processing steps specified in the 3GPP-UMTS Standard TS 25.212 will be explained in more detail in the following text. At the transmitter end, a CRC code is added for each transport block in a set of transport blocks, which are each of the same size. For this purpose, the CRC code generator has four generator polynomials with polynomial degrees 8, 12, 16 and 24, which can be represented as follows:gCRC8(D)=1+D+D3+D4+D7+D8,   (1)gCRC12(D)=1+D+D2+D3+D11+D12,   (2)gCRC16(D)=1+D5+D12+D16,   (3)gCRC24(D)=1+D+D5+D6+D23+D24.   (4)
The choice of one of these polynomials is defined by a decision made at a higher physical level at the transmitter end.
Starting from the m-th transport block (in a set of transport blocks) as a vector of bit length Aam=(am1, am2, . . . , amA),   (5)systematic CRC coding is carried out in accordance with the Standard mentioned above in such a way that the polynomialZm(D)=pmL+pm(L−1)D+ . . . +pm1DL−1+amADL+am2DA+L−2+am1DA+L−1   (6)has a remainder equal to zero when it is divided by the generator polynomial g(D). The bits in the payload signal vector am and the bits which correspond to the remainder polynomialpm(D)=pmL+pm(L−1)D+ . . . +pm1DL−1   (7)are mapped onto a vector bm as follows:bm=(bm1, bm2, . . . , bm(A+L))=(am1, . . . , amA, pmL, . . . , pm1)   (8)
In this case, it can be stated that that bit which corresponds to the highest exponent in equation (6) appears in the least significant position in the vector bm. The payload signal bits appear at the less significant positions in the vector bm and, in contrast, the CRC parity bits appear at the most significant positions. The CRC parity bits are, however, mapped onto the vector bm in their natural sequence, that is to say the coefficients which correspond to the low exponents in the remainder polynomial are mapped onto the less significant positions in bm. In particular, that coefficient pm1 which corresponds to the highest exponent in the remainder polynomial is matched onto the most significant bit position in bm.
A total of M transport blocks such as these which have been provided with CRC parity bits are then linked to one another, and are passed to the channel coder.
The channel decoding process which is carried out at the receiver end can be carried out in various ways. In the case of the known “sliding window method”, the data signals in a block are recovered in the sequence in which they were supplied to the convolutional coder at the transmitter end. In the case of the so-called exact Viterbi traceback operation and in which the Viterbi decoder stores the traceback data over the entire trellis, the data signals in a block are in contrast recovered in the opposite sequence to that in which they were supplied to the convolutional coder at the transmitter end, that is to say in the sequence indicated on the right-hand side of equation (8). The problem is now that the payload signal bits and parity bits which occur in this sequence cannot be passed directly to a conventional CRC error determination circuit, which is formed from a linear feedback shift register. For this reason, the so-called hard decision sequence (which occurs during the Viterbi traceback) of recovered signal data corresponding to the vector bm is first of all stored in a buffer store for one block or for the complete set of collated blocks. The data signals are then called up from the buffer store in the correct sequence, and are passed into the shift register in the CRC error determination circuit. The temporary storage of the values is on the one hand complex in terms of hardware since a corresponding amount of memory space must be made available and, on the other hand, it is associated with a time penalty, since the data must be stored in the memory and must be called up from it again.
The described requirement for temporary storage before carrying out the redundancy check on the basis of the bit sequence taken from the decoding process may, however, likewise occur when the abovementioned sliding window method is used for the Viterbi traceback. In this case as well, it is possible for the parity or redundancy checking bits to be added to the data block and to be obtained from the decoding process at the receiver end in such a way that the bit sequence does not allow the payload data bits and parity bits to be passed directly to the linear feedback shift register for polynomial division.
Furthermore, a situation can occur in which the bit sequence produced by the decoding process is the complete inverse of the sequence of bits in which they would be supplied to a conventional shift register for cyclic redundancy checking in order to carry out a correct polynomial division. In this case as well, the bits are therefore first of all temporarily stored in a complex manner in a buffer store.